#include<vector>
using namespace std;
class Solution {
private:
    int C(int a, int b)
    {
        if(a > b) return 0;
        int up = 1, down = 1;
        for(int i = b - a + 1; i <= b; ++i) up*=i;
        for(int i = 2; i <= a; ++i) down*=i;
        return up/down;
    }
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int last = nums.size() - 1, first = 0;
        int num = 0;
        while(last > 1)
        {
            int second = last - 1, first = 0;
            while(first <= second)
            {
                while(first < second && nums[first] + nums[second] > nums[last]) second--;
            //到这里的时候，要么遍历完了，要么就是已经不满足所需条件了
                num+= last - second - 1;
                //printf("first:%d second:%d last:%d\n",first,second,last);
                if(first == second) num += C(2, last - first - 1);              
                ++first;
            }
            --last;
        }
        return num;
    }
};